This invention relates to garbage collectors that mark live objects concurrently with the operation of user application programs. In general, memory reclamation may be carried out by a special purpose garbage collection algorithm that locates and reclaims memory which is unused, but has not been explicitly de-allocated. There are many known garbage collection algorithms, including reference counting, mark-sweep, mark-compact and generational garbage collection algorithms. These, and other garbage collection techniques, are described in detail in a book entitled “Garbage Collection, Algorithms For Automatic Dynamic Memory Management” by Richard Jones and Raphael Lins, John Wiley & Sons, 1996.
An object may be located by a “reference”, or a small amount of information that can be used to access the object data structure. Objects can themselves contain references to yet other objects. In this manner, a chain of references can be created, each reference pointing to an object which, in turn, points to another object. Some garbage collection techniques determine when a data structure is reachable by an executing program thread by starting at external roots (for example, program stack entries) and following chains of references and marking all objects encountered. After all reference chains have been followed, the memory occupied by unmarked objects can be reclaimed and reused. Object marking may be carried out by a single collector thread or may be carried out by several collector threads operating in parallel. Reclamation of unused memory is generally performed during a “sweep” phase of garbage collection that follows the marking phase.
Some marking garbage collectors stop all application threads while the marking is being performed. However, many applications cannot tolerate the significant pauses that can be introduced while marking is being performed. For example, some applications have multiple gigabytes of live data and must run continuously for months or years with maximum garbage collection pauses measured in milliseconds. A common solution to enabling garbage collection for systems in which such applications run is to employ concurrent collection, in which garbage collection and the user application execute simultaneously. Examples of such collectors are described in “A parallel, incremental and concurrent GC for servers”, Y. Ossia, O. Ben-Yitzhak, I. Goft, E. K. Kolodner, V. Leikehman, and Avi Owshanko. Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, pages 129-140. ACM Press, 2002 and “A generational mostly-concurrent garbage collector”, A. Printezis and D. Detlefs, Proceedings of the International Symposium on Memory Management, Minneapolis, Minn., Oct. 15-19, 2000.
Since the collector and the application threads are operating concurrently and the application threads may modify pointer locations that are used to perform marking by the collector, in any concurrent marking garbage collector, the application threads must inform the collector of pointer updates performed during collection. The aforementioned concurrent marking collectors use a continuous update interaction between the application threads and the collector. In particular, during their operation, application threads inform the collector of pointer locations that they modify, and the collector re-examines the locations of which it has been notified.
Other collectors use an alternative mechanism to manage application thread and collector interactions. This alternative mechanism is called “snapshot-at-the-beginning (SATB) technique, in which at the start of the marking process a logical “snapshot” is taken of a graph representing the existing objects and their relationships. The collector then follows pointers and marks objects in this graph. The application threads help to track changes to this logical snapshot by informing the collector of their actions that might disconnect parts of the original object graph and, thus, prevent the collector from reaching these parts. SATB collectors are described in the aforementioned Jones and Lins book, in particular in section 8.3.
Collectors that use SATB style marking have a major advantage over collectors that use continuous update style marking. In particular, in a SATB style marking collector, all new objects allocated after the marking process has started are considered live, so only modifications to objects already allocated at the start of the marking process need cause collection activity. In contrast, collectors that use continuous update marking must examine all modified marked objects, since any such object could hold a pointer to objects that would otherwise be “hidden” from the concurrent marking process. In general, most programs are “mostly-functional” in that a large proportion of object modifications are initializations of newly-allocated objects. Collectors that use SATB style marking can safely ignore such modifications, while collectors that use the continuous-update marking style must examine them.
In order to determine when a modification has been made to a pointer, a “write barrier” is typically used. A write barrier comprises extra code that is generated by a compiler when it is compiling any application thread code that would produce a write to a pointer location. At runtime, before a write is performed by an application thread, the write barrier code is first executed. The write barrier code can then take an appropriate action, such as informing the collector of the write operation. However, collectors that use SATB style marking have a significant drawback versus collectors that use continuous update style marking because the cost of executing the write barrier code is typically much higher for collectors that use SATB style marking.
More particularly, in collectors that use the continuous update marking style, a common approach is to use a card-marking write barrier, which can require as few as two instructions to be executed in the write barrier code that is executed for each pointer write. Such card marking write barriers are discussed in detail in “A fast write barrier for generational garbage collectors”, U. Hölzle, OOPSLA/ECOOP '93 Workshop on Garbage Collection in Object-Oriented Systems, E. Moss, P. R. Wilson, and B. Zorn, editors, October 1993. In the generational garbage collectors discussed above, card marking write barriers are particularly efficient, since a write barrier must already be present to track the possible creation of old generation to young generation pointers. On the other hand, write barriers for use with collectors that use SATB style marking usually execute much more complicated barrier code that reads the pre-write value of the pointer field and adds this value a data structure that will later be read by a concurrent marking thread.
One method of reducing the code that must be executed by write barriers for use with collectors that use SATB style marking is to check the pre-write value of the pointer field prior to executing the remainder of the write barrier code. Many programming languages provide a special value, here referred to as “NULL”, indicating that a location of pointer type currently contains no pointer value. If the SATB write barrier determines that the write overwrites NULL, there is no pre-write pointer value to log, so the remainder of the barrier code need not be executed. In many languages (e.g., Java and C#), pointer fields of newly allocated objects are initialized to contain NULL. In many applications, the majority of pointer writes are initializing writes and, in these programs, the latter modification can significantly reduce the write barrier cost. Nonetheless, even with this modification, the pointer field must still be retrieved and its value checked. Therefore, write barrier code for use with collectors that use SATB style marking is still more costly than write barrier code for use in collectors that use continuous update style marking.